package DailyPractice.Day29;

/**
 * 最小不可组成和
 * @author lumin
 * @date 2022/05/26 19:58
 **/
import java.util.Scanner;

public class Num1 {
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        while (sc.hasNext()) {
//            int n = sc.nextInt();
//            int[] ary = new int[n];
//            for (int i = 0; i < n; i++) {
//                ary[i] = sc.nextInt();
//            }
//            System.out.println(getFirstUnFormedNum(ary));
//        }
//    }
    public static void main(String[] args) {
        int[] arr = {3,2,5};
        System.out.println(getFirstUnFormedNum(arr));
    }
    public static int getFirstUnFormedNum(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            max += arr[i];
            min = Math.min(min, arr[i]);
        }
        boolean res[] = new boolean[max + 1];
        res[0] = true; // 为了使单个元素去求和时是真的 (i + 0 = i)
        for (int i = 0; i < arr.length; i++) {
            for (int j = max; j >= arr[i]; j--) {
                res[j] = res[j - arr[i]] || res[j];
            }
        }

        for (int i = min; i < res.length; i++) {
            if (!res[i])
                return i;
        }
        return max + 1;
    }
}

